package es.unileon.TIC;

import java.util.ArrayList;

/**
 * CODIFICACI�N HUFFMAN
 * 
 * El objetivo del trabajo es estudiar el ratio de compresi�on de una
 * codificaci�on binaria optima de un mensaje con respecto a la codificaci�on de
 * 8 bits ASCII. El dato dE partida va a ser un mensaje m de texto. Trabajando
 * con el dato de partida ten�is que: 
 * 		- Calcular la fuente F asociada al mensaje m. 
 * 		- Calcular una codificaci�n binaria �ptima para F y usarla para codificar m. 
 * 		- Calcular el ratio de compresi�n de la codificaci�n anterior con respecto a 
 * 		  la codificaci�n de 8 bits ASCII.
 * 
 * @author Guillermo Montero Jubete
 * @author Adrian Santos Rebaque
 * @author Pablo Tejedor Garc�a
 * 
 */

public class Huffman {

	/**
	 * Una vez recibido el mensaje, calculamos la tabla de frecuencias (Fuente).
	 * 
	 * @param mensaje
	 * @return fuente
	 */
	public static ArrayList<Frecuencias> calculaFuente(String mensaje) {
		boolean encontrado=false;
		int j=0;
		ArrayList<Frecuencias> fuente = new ArrayList<Frecuencias>(); //ArrayList fuente
		//Recorremos el mensaje
		for(int i=0;i<mensaje.length();i++)
			if(fuente.size()==0){//Si fuente es null, a�adimos la primera frecuencia
				fuente.add(new Frecuencias(mensaje.charAt(i),1));
			}else{//Si fuente no es null
				while(j<fuente.size() && encontrado==false){//Recorremos fuente
					if(fuente.get(j).getCaracter()!=mensaje.charAt(i)){//si el elemento no esta en fuente
						encontrado=false;
					}else{//Si el elemento esta en fuente, aumentamos frecuencia
						fuente.get(j).setFrecuencia(fuente.get(j).getFrecuencia()+1);
						encontrado=true;
					}
					j++;
				}
				if(!encontrado)//Si no habiamos encontrado el elemento, lo a�adimos 
					fuente.add(new Frecuencias(mensaje.charAt(i),1));
				//Inicializamos variables
				encontrado=false;
				j=0;
			}

		return fuente;
	}
	
	public static ArrayList<Frecuencias> ordenar(ArrayList<Frecuencias> fuente){
		        Frecuencias temp;
		        int t = fuente.size();
		        for (int i = 1; i < t; i++) {
		            for (int k = t- 1; k >= i; k--) {
		                if(fuente.get(k).getFrecuencia() < fuente.get(k-1).getFrecuencia()){
		                    temp = fuente.get(k);
		                    fuente.set(k, fuente.get(k-1));
		                    fuente.set(k-1,temp);
		                }//fin if
		            }// fin 2 for
		        }//fin 1 for
		        return fuente;
		    }//fin
	
	public static void listar(ArrayList<Frecuencias> fuente) {
		for(int k=0;k<fuente.size();k++)
			System.out.println(fuente.get(k));
		System.out.println("-----------------");
	}
	
	public static void agrupar(ArrayList<Frecuencias> fuente){
		Frecuencias padre,hijoi,hijod;
			hijoi = fuente.get(0);
			fuente.remove(0);
			hijod = fuente.get(0);
			fuente.remove(0);
			padre = new Frecuencias(hijoi.getFrecuencia()+hijod.getFrecuencia(),hijoi,hijod);
			fuente.add(padre);
			ordenar(fuente);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		String mensaje = "tres tristes tigres";
		ArrayList<Frecuencias> fuente = new ArrayList<Frecuencias>();
		
		fuente = calculaFuente(mensaje);
		
		listar(fuente);
		ordenar(fuente);
		listar(fuente);
		
		while(fuente.size() >= 2) {
			agrupar(fuente);
		}
		listar(fuente);

		//calculaCodificacionBinaria(fuente.get(0), new StringBuffer());
	}

	

}
